package com.ryujung.array.leetCode_4;
/*
 * @lc app=leetcode.cn id=4 lang=java
 *
 * [4] 寻找两个正序数组的中位数
 */

import java.util.Arrays;

// @lc code=start
class Solution {

    /**
     * 思路1： 直接将两个数组全部放入一个列表中，然后对列表进行排序，获取中位数
     * 时间复杂度：O(m + n)
     * 空间复杂度：O(m + n)
     */
    public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        int[] arr = new int[len];
        for (int i = 0; i < nums1.length; i++) {
            arr[i] = nums1[i];
        }
        for (int i = nums1.length; i < len; i++) {
            arr[i] = nums2[i - nums1.length];
        }
        Arrays.sort(arr);
        double result = len % 2 == 1 ? arr[len / 2] : (double) (arr[len / 2] + arr[len / 2 - 1]) / 2;

        return result;
    }

    /**
     * 思路2：使用二分法，且不使用第三个数组，逼近中位数(就地修改)
     * 步骤：直接对比数组1 和数组2 的第i个数字，
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
        return 0d;
    }

    public static void main(String[] args) {
        int[] arr1 = { 1, 3 };
        int[] arr2 = { 2 };
        System.out.println(findMedianSortedArrays(arr1, arr2));
    }

}
// @lc code=end
